# # -*- coding:utf-8
# 5170. 验证二叉树 显示英文描述
# 用户通过次数0
# 用户尝试次数0
# 通过次数0
# 提交次数0
# 题目难度Medium
# 二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。
#
# 只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时，返回 true；否则返回 false。
#
# 如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。右子节点也符合该规则。
#
# 注意：节点没有值，本问题中仅仅使用节点编号。

from typing import List
class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        ##使用bfs的思路

        visited = [0 for _ in range(n)]
        qqq = [0]
        visited[0] = 1

        while len(qqq)>0:
            node = qqq.pop(0)
            if leftChild[node] == -1:
                print(node," left:-1")
            else:
                qqq.append(leftChild[node])
                if visited[leftChild[node]]>0: ##已访问过的节点
                    return False
                else:
                    visited[leftChild[node]] += 1


            if rightChild[node] == -1:
                print(node," right:-1")
            else:
                qqq.append(rightChild[node])
                if visited[rightChild[node]]>0: ##已访问过的节点
                    return False
                else:
                    visited[rightChild[node]] += 1


        return sum(visited) == n



